GATE CSE 2007
Q1.
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?Q2.
Consider the following C code segment: int IsPrime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i == 0) {printf("Not Primen"); return 0;} return 1; } Let T(n)denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?Q3.
In the following C function, let n\geqm. int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?Q4.
What is the Asymptotic Notation of the following recursive function: int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }Q5.
Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value = value + GetValue(ptr->leftChild) + GetValue(ptr->rightChild); } return(value); } The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:Q6.
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The postorder traversal of the binary tree is:Q7.
The maximum number of binary trees that can be formed with three unlabeled nodes is:Q8.
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:Q10.
A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?